﻿#include "header.h"

/*

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

示例 :

给定这个链表：1->2->3->4->5
当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5

说明 :
你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。


*/

class Solution {
public:
	ListNode *reverseKGroup(ListNode *head, int k)
	{
		if (!head || !head->next || k == 1) return head;
		ListNode *dummy = new ListNode(-1);
		dummy->next = head;
		ListNode *ahead = dummy;
		int i = 1;
		while (head)
		{
			if (i%k == 0)
			{
				ahead = reverse(ahead, head->next);
				head = ahead->next;
			}
			else
			{
				head = head->next;
			}
			++i;
		}
		ListNode *listHead = dummy->next;
		delete dummy;
		return listHead;
	}
	ListNode *reverse(ListNode *ahead, ListNode *behind)
	{
		ListNode *start = ahead->next;
		ListNode *then = start->next;
		ListNode *pre = ahead;
		while (then != behind)
		{
			start->next = then->next;
			then->next = pre->next;
			pre->next = then;
			then = start->next;
		}
		return start;
	}
};
//根据题目092.reverse-linked-list-ii，先得出在一个区间内翻转链表，然后再求出每个区间即可。